package com.chj.gaoji.class10;

import java.io.IOException;

public class Code03_NiuNiuSplitField {
//	首先感谢@元气の悟空 同学分享的代码，我没有看这份源码之前只想到了强行遍历的方法，
//	最后应该是n^6的时间复杂度，但是他分享的方法在获取最小值的最大值的部分做了优化
//	时间复杂度只有n^4方
//	简述核心思路，1确认可能的取值范围 1 到 土地计算值/16，我们需要确认一个x，我们能
//	将土地划分至16个计算值大于x的区域
//	2 在确认了x之后，我们可以只遍历一个方向上的划分方案，在第二个方向上尝试划分的时
//	候，我们可以基于[如果我们前k块划走的区域足够小的时候，那么这种情况下后面n-k块的
//	最佳划分不会劣于前k块划走更多区域的时候的划分]，这句话可能看起来比较绕，结合代码
//	看会更加清楚一些。
//	下面是我加了注释之后的代码，在元气の悟空同学的基础上做了一点优化。

//	int main() {
//	    scanf("%d%d", &n, &m);
//	    for (int i = 0; i<n; scanf("%s", field[i]), i++);
//	    printf("%d\n", solve());
//	}

	public static void main(String[] args) throws IOException {
		int n = 4;
		int m = 4;

		int[][] matrix = new int[][] { { 0, 0, 0, 0, 0 }, { 0, 3, 3, 3, 2 }, { 0, 3, 2, 3, 3 }, { 0, 3, 3, 3, 2 },
				{ 0, 2, 3, 2, 3 } };
		System.out.println(solve(n, m, matrix));
	}

	public static int solve(int n, int m, int[][] G) {
		// 将字符数组 转化为数字数组
		int i, j;
//		for (i = 1; i <= n; i++)
//			for (j = 1; j <= m; j++)
//				G[i][j] = field[i - 1][j - 1] - '0';
//		int Max = 0;
		// 生成横向与纵向都包含队首元素的区域的计算值
		int[][] area = new int[n + 1][m + 1];
		area[1][1] = G[1][1];
		for (j = 2; j <= m; j++)
			area[1][j] = G[1][j] + area[1][j - 1];
		for (i = 2; i <= n; i++)
			area[i][1] = G[i][1] + area[i - 1][1];
		// 动态计算所有从左上角开始的区域的值
		for (i = 2; i <= n; i++) {
			for (j = 2; j <= m; j++) {
				area[i][j] = G[i][j] + area[i - 1][j] + area[i][j - 1] - area[i - 1][j - 1];
			}
		}
		int l = 0, r = area[n][m] / 16 + 1;

		// 二分法遍历，锁定满足条件的值
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			if (isAreaOk(mid, n, m, area))
				l = mid;
			else
				r = mid;
		}
		// if (isAreaOk(r)) return r;
		return l;
	}

	// 计算(i,j) 到（k，q）区域的计算值
	public static int getA(int i, int j, int k, int q, int[][] area) {
		return area[k][q] - area[i - 1][q] - area[k][j - 1] + area[i - 1][j - 1];
	}

	// 判断按照给定的行的切分方式是否能够满足要求
	public static boolean judge(int i, int j, int k, int x, int n, int m, int[][] area) {
		// 采用遍历的方式，尝试是否能切成16块能够满足计算值>x的区域
		// 首先方法输入已经给出来矩阵行上的限制，所以在尝试纵向切分的时候采取了贪婪的方式，每一块区域足够小
		int q, cnt = 0, pre = 0;
		for (q = 1; q <= m; q++) {
			int x1 = getA(1, pre + 1, i, q, area), x2 = getA(i + 1, pre + 1, j, q, area);
			int x3 = getA(j + 1, pre + 1, k, q, area), x4 = getA(k + 1, pre + 1, n, q, area);
			if (x1 >= x && x2 >= x && x3 >= x && x4 >= x) {
				pre = q;
				cnt++;
				if (cnt == 4)
					break;
			}
		}
		return cnt == 4;
	}

	// 判断土地是否能切分出计算值大于x的16块
	public static boolean isAreaOk(int x, int n, int m, int[][] area) {
		// 遍历行上面的切分方式
		int i, j, k;
		for (i = 1; i < n; i++)
			for (j = i + 1; j < n; j++)
				for (k = j + 1; k < n; k++)
					if (judge(i, j, k, x, n, m, area))
						return true;
		return false;
	}
}
